#include "leetcode/leetcode.h"

class Solution {
public:
    int longestValidParentheses(string s) {

        if(s.empty()) return 0;
        
        stack<int> left_pos({-1});
        int max_vaild_length = 0;

        for(int i=0; i<s.size(); i++){
            if(s[i] == '('){
                left_pos.push(i);
            }
            else{
                left_pos.pop();
                if(left_pos.empty()){
                    left_pos.push(i);
                }
                else{
                    max_vaild_length = max(i - left_pos.top(), max_vaild_length); 
                }
            }

        }

        return max_vaild_length;
    }
};

class Solution1 {
public:
    int longestValidParentheses(string s) {

        vector<int> dp(s.size(), 0);
        int max_vaild_length = 0;
        for(int i=1; i<s.size(); i++){
            if(s[i] == ')'){
                if(s[i-1] == '('){
                    dp[i] = (i>=2? dp[i-2]: 0) + 2;
                }
                else if(i-1-dp[i-1]>=0 && s[i-1-dp[i-1]] == '('){
                    dp[i] = dp[i-1] + (i-dp[i-1]-1 > 0? dp[i-dp[i-1]-2] : 0) + 2;
                }
            }
            max_vaild_length = max(dp[i], max_vaild_length);
        }

        return max_vaild_length;
    }
};